package q86_partition;

import CommonClass.Common.ListNode;

public class Solution_1 {
    /*
    对链表按照某个值进行分割
    这里主要分成了两个步骤
     */
    public ListNode partition(ListNode head, int x) {
        // 先判空
        if (head == null || head.next == null) {
            return head;
        }

        // 创建哑节点
        ListNode dummy = new ListNode(0 ,head);
        // 建立cur节点
        ListNode cur = dummy;
        // 1 第一步 先不停后移cur 直至cur.next是一个大于x的值
        while (cur.next != null && cur.next.val < x) {
            cur = cur.next;
        }

        // 此时将cur节点作为一个前引节点 创建一个p节点为cur.next
        ListNode p = cur.next;
        // 2 当p.next != null时进行判断
        while (p != null && p.next != null) {
            // 如果其next是一个大于x的值 则不停后移p
            if (p.next.val >= x) {
                p = p.next;
            }else {
                // 否则就将p的next节点断开 并移动到cur节点后
                // 然后cur节点后移
                ListNode temp = p.next;
                p.next = p.next.next;
                temp.next = cur.next;
                cur.next = temp;
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}
